import java.util.Arrays;

public class LeetCode1893 {

    public static void main(String[] args) {
        int[][] ranges = {{1, 2}, {3, 4}, {5, 6}};
        int left = 2, right = 5;

        System.out.println(isCovered(ranges, left, right));
    }

    public static boolean isCovered(int[][] ranges, int left, int right) {
        boolean[] flag = new boolean[51];
        for (int[] range : ranges) {
            for (int i = range[0]; i <= range[1]; i++) {
                flag[i] = true;
            }
        }
        for (int i = left; i <= right; i++) {
            if (!flag[i]) {
                return false;
            }
        }
        return true;
    }

    public static boolean isCovered1(int[][] ranges, int left, int right) {
        Arrays.sort(ranges, (a1, a2) -> a1[0] - a2[0]);
        for (int[] range : ranges) {
            int l = range[0];
            int r = range[1];
            Arrays.stream(range).forEach(System.out::println);
            if (l <= left && left <= r) {
                left = r + 1;
            }
        }
        return left > right;
    }

    public static boolean isCovered2(int[][] ranges, int left, int right) {
        boolean[] flag = new boolean[51];
        for (int[] range : ranges) {
            int L = Math.max(left, range[0]);
            int R = Math.min(right, range[1]);
            for (int i = L; i <= R; i++) {
                flag[i] = true;
            }
        }
        for (int i = left; i <= right; i++) {
            if (!flag[i]) {
                return false;
            }
        }
        return true;
    }

    public static boolean isCovered3(int[][] ranges, int left, int right) {
        int[] diff = new int[52];
        // 对差分数组进行处理
        for (int i = 0; i < ranges.length; i++) {
            diff[ranges[i][0]]++;
            diff[ranges[i][1] + 1]--;
        }
        // 根据差分数组处理前缀和，为理解方便单独定义sum，可以原地做
        int[] sum = new int[52];
        for (int i = 1; i < 52; i++) {
            sum[i] = sum[i - 1] + diff[i];
        }
        // 从 left 到 right 判断是否满足 sum > 0
        for (int i = left; i <= right; i++) {
            if (sum[i] <= 0) {
                return false;
            }
        }
        return true;
    }
}
